package com.ztom.top100;

/**
 * 单词搜索
 * <p>
 * https://leetcode-cn.com/problems/word-search/
 *
 * @author ZhangTao
 */
public class Code34Exist {

    public boolean exist(char[][] board, String word) {
        if (board == null || board.length == 0 || board[0].length == 0 || word == null || word.length() == 0) {
            return false;
        }
        int m = board.length;
        int n = board[0].length;
        boolean[][] visited = new boolean[m][n];
        char[] str = word.toCharArray();
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (check(board, visited, i, j, str, 0)) {
                    return true;
                }
            }
        }
        return false;
    }

    private boolean check(char[][] board, boolean[][] visited, int i, int j, char[] word, int index) {
        if (board[i][j] != word[index]) {
            // 当前位置不相等
            return false;
        } else if (index == word.length - 1) {
            // 当前位置相等 且 word 匹配到最后一个字符
            return true;
        }
        // 当前位置已匹配过
        visited[i][j] = true;
        // 上下左右四个方向去匹配
        boolean result =
                i - 1 >= 0 && !visited[i - 1][j] && check(board, visited, i - 1, j, word, index + 1)
                ||
                i + 1 < board.length && !visited[i + 1][j] && check(board, visited, i + 1, j, word, index + 1)
                ||
                j - 1 >= 0 && !visited[i][j - 1] && check(board, visited, i, j - 1, word, index + 1)
                ||
                j + 1 < board[0].length && !visited[i][j + 1] && check(board, visited, i, j + 1, word, index + 1);

        // 回溯
        visited[i][j] = false;
        return result;
    }
}
